home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / fortran / toolpack.000 / toolpack / toolpack1.2 / tables / ZBTALL.MAC.f < prev    next >
Encoding:
Text File  |  1989-03-04  |  7.9 KB  |  325 lines
  1. C---------------------------------------------------------
  2. C    TOOLPACK/1    Release: 1.1
  3. C---------------------------------------------------------
  4. C
  5. C  ZBTADD - 05 MAR 84
  6. C           TIE LIBRARY
  7. C           TABLES SUPPLEMENTARY LIBRARY
  8. C
  9. C  ADD AN ELEMENT TO THE BINARY TREE
  10. C
  11. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR 'NOERR'
  12. C
  13.       INTEGER FUNCTION ZBTADD(PLACE, VALUES, ARRAY)
  14.  
  15.       INTEGER PLACE, I, POINT, OFFSET, ROOM
  16.       INTEGER ARRAY(*), VALUES(*)
  17.  
  18. C  CHECK LEGALITY OF REQUEST. MUST BE CURRENTLY AT A NODE THAT
  19. C  HAS A FREE SLOT IN THE REQUESTED BRANCH POSITION.
  20.       ZBTADD = -1
  21.       IF(ARRAY(1) .NE. 98) RETURN
  22.  
  23.       IF(PLACE .EQ. 108) THEN
  24.         IF(ARRAY(ARRAY(5)    ) .NE. 0) RETURN
  25.         OFFSET = 0
  26.       ELSE IF(PLACE .EQ. 114) THEN
  27.         IF(ARRAY(ARRAY(5) + 1) .NE. 0) RETURN
  28.         OFFSET = 1
  29.       ELSE
  30.         RETURN
  31.       ENDIF
  32.  
  33. C  CHECK TO SEE IF THERE IS ENOUGH SPACE. NOTE THAT IF THE MAXIMUM
  34. C  DEPTH OF THE TREE IS ABOUT TO BE INCREASED THEN AN ADJUSTMENT TO
  35. C  THE CALCULATION IS MADE.
  36.       ZBTADD = -100
  37.       ROOM = (ARRAY(2) - 8 - ARRAY(7))
  38.       IF(ARRAY(6) .EQ. ARRAY(7)) ROOM = ROOM - 1
  39.       ROOM = ROOM / (ARRAY(3) + 2)
  40.       IF(ARRAY(4) .EQ. ROOM) RETURN
  41.  
  42.       IF(ARRAY(6) .EQ. ARRAY(7)) ARRAY(7) = ARRAY(7) + 1
  43.       POINT = 9 + (ARRAY(4) * (ARRAY(3) + 2))
  44.  
  45. C  SET UP THE NEW NODE AND LINK IT IN TO THE TREE.
  46.       ARRAY(POINT)             = 0
  47.       ARRAY(POINT + 1)         = 0
  48.       ARRAY(ARRAY(5) + OFFSET) = POINT
  49.  
  50.       DO 10 I = 1, ARRAY(3)
  51.         ARRAY(POINT + 1 + I) = VALUES(I)
  52.    10 CONTINUE
  53.  
  54. C  INCREASE THE COUNT OF ENTRIES
  55.       ARRAY(4) = ARRAY(4) + 1
  56.       ZBTADD = -2
  57.  
  58.       RETURN
  59.       END
  60. C----------------------------------------------------------------------
  61. C
  62. C  ZBTINT - 05 MAR 84
  63. C           TIE LIBRARY
  64. C           TABLES SUPPLEMENTARY LIBRARY
  65. C
  66. C  INITIALISE AN ARRAY AS A BINARY TREE
  67. C
  68. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' (THE SIZE OF THE ARRAY
  69. C  OR SPECIFIED WIDTH IS WRONG) OR 'NOERR'. THERE IS
  70. C  AN OVERHEAD OF 8 LOCATIONS RESERVED BY THE ROUTINES.
  71. C  AN ADDITIONAL OVERHEAD OF 2 LOCATIONS PER TREE ENTRY IS USED TO
  72. C  RETAIN THE POINTERS. A STACK IS HELD AT THE END OF THE ARRAY.
  73. C
  74.       INTEGER FUNCTION ZBTINT(ARRAY, SIZE, WIDTH, ROTVAL)
  75.  
  76.       INTEGER SIZE, WIDTH, I
  77.       INTEGER ARRAY(*), ROTVAL(*)
  78.  
  79.       ZBTINT = -1
  80.       IF(WIDTH .LE. 0)          RETURN
  81.       IF(SIZE  .LT. WIDTH + 11) RETURN
  82.  
  83. C  IDENTIFY THE ARRAY AS A BINARY TREE
  84.       ARRAY(1) = 98
  85. C  THE SIZE OF THE ARRAY
  86.       ARRAY(2) = SIZE
  87. C  THE WIDTH OF EACH ELEMENT
  88.       ARRAY(3) = WIDTH
  89. C  THE NUMBER OF ENTRIES
  90.       ARRAY(4) = 1
  91. C  THE CURRENT NODE POINTER
  92.       ARRAY(5) = 9
  93. C  THE CURRENT LEVEL (1 = ROOT, 0 = ZBTNXT NOT CALLED YET)
  94.       ARRAY(6) = 0
  95. C  THE MAXIMUM SIZE OF STACK/DEPTH OF TREE
  96.       ARRAY(7) = 1
  97. C  THE CURRENT NUMBER OF STACK ENTRIES
  98.       ARRAY(8) = 0
  99.  
  100. C  SET UP THE ROOT NODE
  101.       ARRAY(9)  = 0
  102.       ARRAY(10) = 0
  103.       DO 10 I = 1, WIDTH
  104.         ARRAY(10 + I) = ROTVAL(I)
  105.    10 CONTINUE
  106.  
  107.       ZBTINT = -2
  108.  
  109.       RETURN
  110.       END
  111. C-----------------------------------------------------------
  112. C
  113. C  ZBTNXT - 05 MAR 84
  114. C           TIE LIBRARY
  115. C           TABLES SUPPLEMENTARY LIBRARY
  116. C
  117. C  GO TO THE NEXT NODE OF THE TREE
  118. C
  119. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR THE FREE
  120. C  SIBLING POINTER INFORMATION
  121. C
  122.       INTEGER FUNCTION ZBTNXT(VALUES, ARRAY)
  123.  
  124.       INTEGER I
  125.       INTEGER ARRAY(*), VALUES(*)
  126.  
  127. C  CHECK LEGALITY OF REQUEST
  128.       ZBTNXT = -1
  129.       IF(ARRAY(1) .NE. 98) RETURN
  130.  
  131. C  IF THE TREE POINTER HAS JUST BEEN RESET THEN MOVE TO THE FIRST
  132. C  POSITION, OTHERWISE SKIP DIRECT TO CHECKING THE RIGHT BRANCH.
  133.       IF(ARRAY(6) .NE. 0) GO TO 40
  134.       ARRAY(6) = 1
  135.  
  136.    30 CONTINUE
  137.    10 CONTINUE
  138.         IF(ARRAY(ARRAY(5)) .NE. 0) THEN
  139.           ARRAY(ARRAY(2) - ARRAY(8)) = ARRAY(5)
  140.           ARRAY(8) = ARRAY(8) + 1
  141.           ARRAY(6) = ARRAY(6) + 1
  142.           ARRAY(5) = ARRAY(ARRAY(5))
  143.           GO TO 10
  144.         ENDIF
  145.       DO 20 I = 1, ARRAY(3)
  146.         VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
  147.    20 CONTINUE
  148.       GO TO 100
  149.  
  150.    40 CONTINUE
  151.  
  152. C  NORMAL START OF PROCESSING. IF IT IS POSSIBLE TO TAKE A RIGHT BRANCH
  153. C  THEN DO SO AND FIND ITS LEFT MOST DECSENDENT.
  154.       IF(ARRAY(ARRAY(5) + 1) .NE. 0) THEN
  155.         ARRAY(5) = ARRAY(ARRAY(5) + 1)
  156.         ARRAY(6) = ARRAY(6) + 1
  157.         GO TO 30
  158.       ENDIF
  159.  
  160. C  IF THE STACK IS EMPTY THEN THIS IS THE END OF THE LINE
  161.       IF(ARRAY(8) .EQ. 0) THEN
  162.         ZBTNXT = -100
  163.         RETURN
  164.  
  165. C  POP AN ELEMENT OFF THE STACK AND CONTINUE
  166.       ELSE
  167.         ARRAY(8) = ARRAY(8) - 1
  168.         ARRAY(5) = ARRAY(ARRAY(2) - ARRAY(8))
  169.         ARRAY(6) = ARRAY(6) - 1
  170.         DO 50 I = 1, ARRAY(3)
  171.           VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
  172.    50   CONTINUE
  173.         GO TO 100
  174.  
  175.       ENDIF
  176.  
  177.   100 CONTINUE
  178.       ZBTNXT = -2
  179.  
  180.       RETURN
  181.       END
  182. C-----------------------------------------------------------------
  183. C
  184. C  ZBTRST - 05 MAR 84
  185. C           TIE LIBRARY
  186. C           TABLES SUPPLEMENTARY LIBRARY
  187. C
  188. C  INITIALISE THE POINTER AND RECOVERY ORDER FOR THE BINARY TREE.
  189. C
  190. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
  191. C
  192.       INTEGER FUNCTION ZBTRST(ARRAY)
  193.  
  194.       INTEGER ARRAY(*)
  195.  
  196.       ZBTRST = -1
  197.       IF(ARRAY(1) .NE. 98) RETURN
  198.  
  199. C  THE CURRENT NODE POINTER
  200.       ARRAY(5) = 9
  201. C  THE CURRENT LEVEL (0 = ROOT)
  202.       ARRAY(6) = 0
  203. C  THE STACK POINTER
  204.       ARRAY(8) = 0
  205.  
  206.       ZBTRST = -2
  207.  
  208.       RETURN
  209.       END
  210. C--------------------------------------------------------------
  211. C
  212. C  ZBTTYP - 05 MAR 84
  213. C           TIE LIBRARY
  214. C           TABLES SUPPLEMENTARY LIBRARY
  215. C
  216. C  RETURN INFORMATION ABOUT A BINARY TREE
  217. C
  218. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
  219. C
  220.       INTEGER FUNCTION ZBTTYP(ARRAY, WIDTH, ENTRYS, FREE)
  221.  
  222.       INTEGER ENTRYS, FREE, WIDTH
  223.       INTEGER ARRAY(*)
  224.  
  225.       ZBTTYP = -1
  226.       IF(ARRAY(1) .NE. 98) RETURN
  227.  
  228. C  THE WIDTH OF EACH ELEMENT
  229.       WIDTH  = ARRAY(3)
  230. C  THE NUMBER OF ENTRIES
  231.       ENTRYS = ARRAY(4)
  232. C  THE MAXIMUM NUMBER OF ENTRIES
  233.       FREE = (ARRAY(2) - 8 - ARRAY(7)) / (ARRAY(3) + 2)
  234.       FREE = FREE - ENTRYS
  235.  
  236.       ZBTTYP = -2
  237.  
  238.       RETURN
  239.       END
  240. C-----------------------------------------------------------
  241. C
  242. C  ZBTBRA - 05 MAR 84
  243. C           TIE LIBRARY
  244. C           TABLES SUPPLEMENTARY LIBRARY
  245. C
  246. C  DIRECTED TREE TRAVERSAL
  247. C
  248. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR THE FREE
  249. C  SIBLING POINTER INFORMATION
  250. C
  251.       INTEGER FUNCTION ZBTBRA(DIRECT, VALUES, ARRAY)
  252.  
  253.       INTEGER  DIRECT, I, TEMP
  254.       INTEGER  ARRAY(*), VALUES(*)
  255.       INTEGER  ZBTRST
  256.       EXTERNAL ZBTRST
  257.  
  258. C  CHECK LEGALITY OF REQUEST
  259.       ZBTBRA = -1
  260.       TEMP = ARRAY(5)
  261.       IF(ZBTRST(ARRAY) .EQ. -1) RETURN
  262.  
  263.       IF(DIRECT .EQ. 108) THEN
  264.         IF(ARRAY(TEMP) .EQ. 0) RETURN
  265.         ARRAY(5) = ARRAY(TEMP)
  266.  
  267.       ELSE IF(DIRECT .EQ. 114) THEN
  268.         IF(ARRAY(TEMP + 1) .EQ. 0) RETURN
  269.         ARRAY(5) = ARRAY(TEMP + 1)
  270.  
  271.       ELSE
  272.         ARRAY(5) = TEMP
  273.         ZBTBRA = -1
  274.  
  275.       ENDIF
  276.  
  277.       DO 20 I = 1, ARRAY(3)
  278.         VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
  279.    20 CONTINUE
  280.  
  281.       IF(ARRAY(ARRAY(5)) .EQ. 0) THEN
  282.         ZBTBRA = 108
  283.         IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTBRA = 98
  284.       ELSE
  285.         ZBTBRA = 102
  286.         IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTBRA = 114
  287.       ENDIF
  288.  
  289.       RETURN
  290.       END
  291. C-----------------------------------------------------------------
  292. C
  293. C  ZBTTOP - 05 MAR 84
  294. C           TIE LIBRARY
  295. C           TABLES SUPPLEMENTARY LIBRARY
  296. C
  297. C  INITIALISE THE TREE FOR DIRECTED TRAVERSAL
  298. C
  299. C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
  300. C
  301.       INTEGER FUNCTION ZBTTOP(VALUES, ARRAY)
  302.  
  303.       INTEGER  I
  304.       INTEGER  ARRAY(*), VALUES(*)
  305.       INTEGER  ZBTRST
  306.       EXTERNAL ZBTRST
  307.  
  308.       ZBTTOP = -1
  309.       IF(ZBTRST(ARRAY) .EQ. -1) RETURN
  310.  
  311.       DO 10 I = 1, ARRAY(3)
  312.         VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
  313.    10 CONTINUE
  314.  
  315.       IF(ARRAY(ARRAY(5)) .EQ. 0) THEN
  316.         ZBTTOP = 108
  317.         IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTTOP = 98
  318.       ELSE
  319.         ZBTTOP = 102
  320.         IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTTOP = 114
  321.       ENDIF
  322.  
  323.       RETURN
  324.       END
  325.